/*
 * Copyright 2012 Sebastian Gesemann. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright notice,
 *      this list of conditions and the following disclaimer.
 *   2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY SEBASTIAN GESEMANN ''AS IS'' AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL SEBASTIAN GESEMANN OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include "tfec3.h"
#include "crc.h"

/*                           FRAME (32bytes)
 *  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 *  |      MID      | ...........24 bytes of fragment data...........
 *  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 *  ............................................... | METAD | CRC16 |
 *  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 *
 *  15        METAD (16bits)       0      MID = message ID
 *  +-------+-----------+-----------+       S = size in fragments (1-15)
 *  |   S   |     0     |    FNUM   |    FNUM = fragment number   (0-17)
 *  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   CRC16 = checksum for whole frame
 *
 *  For frames with S <= FNUM, the frame transports recovery data
 *  generated by TFEC3. The purpose of MID is to identify which fragments
 *  belong to the same message. The message size S must also be the same
 *  for all fragments of the same message. The supported message size is
 *  therefore 24 bytes * 15 fragments = 360 bytes. For such large messages
 *  it seems like a good idea to add 20% of redundancy (3 additional
 *  fragments). For smaller messages a fewer number of recovery fragments
 *  can be used.
 */

#define MIN(x,y) ((y)<(x)?(y):(x))

#define WORDS_PER_FRAGMENT   6
#define BYTES_PER_FRAGMENT  (WORDS_PER_FRAGMENT*4)
#define MAX_DATA_FRAGMENTS  15
#define MAX_RECOV_FRAGMENTS  3
#define MAX_MESSAGE_SIZE    (BYTES_PER_FRAGMENT*MAX_DATA_FRAGMENTS)
#define FRAME_BUFF_SIZE     (MAX_DATA_FRAGMENTS+MAX_RECOV_FRAGMENTS)

struct frame {
	tfec3_u32 mid;
	tfec3_u32 fragmentdata[WORDS_PER_FRAGMENT];
	unsigned short metad;
	unsigned short crc16;
};

#define NUM_DATA_FRAGS(pf)  ((pf)->metad >> 12)
#define FRAGMENT_INDEX(pf)  ((pf)->metad &  63)

static unsigned compute_frame_crc(const struct frame *pf)
{
	return crc16_update(0xFFFF,
		4+                    /* message id */
		4*WORDS_PER_FRAGMENT+ /* fragment data */
		2,                    /* metad */
		pf);
}

static void print_frame(const struct frame *pf)
{
	int j,i;
	const char *p;
	p=(const char*) pf;
	for (i = 0; i < 32; i++)
	   printf ("%02x(%c) ", p[i], p[i] < 32 ? '.' : p[i] > 127 ? '.' : p[i]);
	              
	printf("MID=%08X, [",pf->mid);
	p = (const char*) pf->fragmentdata;
	for (j=0; j<BYTES_PER_FRAGMENT; ++j) {
		if (32<=p[j] && p[j]<127)
			printf("%c",p[j]);
		else
			printf(".");
	}
	printf("], METAD=%04X, CRC16=%04X\n",pf->metad,pf->crc16);
}

/* frame buffer for reception and transmission */
static struct frame  tx_frame[FRAME_BUFF_SIZE];
static unsigned char tx_valid[FRAME_BUFF_SIZE];
static short send_count = 0; /* number of frames to send */
static short send_next  = 0; /* next frame to send */

/**
 * message send preparation (fragmenting and framing)
 *
 * The function takes a "message" up to MAX_MESSAGE_SIZE bytes, chops it up
 * into fragments and adds a little redundancy and overwrites the send
 * buffer's frames
 *
 * @param n
 *   Size of message in bytes (1...MAX_MESSAGE_SIZE)
 * @param msg
 *   Pointer to message
 * @param redundancy_percentage
 *   Percentage of redundancy fragments (0...20). For short messages you can
 *   actually use redundancies up to 300. But no more than three redundancy
 *   fragments are added to the frame buffer.
 * @return
 *   the actual percentage of redundancy that has been generated
 */
int prepare_send_message(int n, const char msg[], int redundancy_percentage)
{
	tfec3_u32 mid;
	unsigned s, k, i, c;
	tfec3_u32 *fragdatas[FRAME_BUFF_SIZE];
	memset(tx_valid,0,sizeof tx_valid);
	assert(0<n && n<=MAX_MESSAGE_SIZE);
	mid = 0x1729BEEF; /* we should pick a message id at random!!! */
	s = (n+BYTES_PER_FRAGMENT-1)/BYTES_PER_FRAGMENT; /* # of user fragments */
	k = MIN(3,(s*redundancy_percentage+99)/100);     /* # of redundancy fragments */
	i = 0;
	while (n>0) {
		tx_frame[i].mid = mid;
		tx_frame[i].metad = (s<<12) + i;
		fragdatas[i] = tx_frame[i].fragmentdata;
		c = MIN(BYTES_PER_FRAGMENT,n); /* chunk of data to copy */
		if (c<BYTES_PER_FRAGMENT)
			memset(fragdatas[i],0,BYTES_PER_FRAGMENT);
		memcpy(fragdatas[i],msg,c);
		tx_frame[i].crc16 = compute_frame_crc(tx_frame+i);
		tx_valid[i] = 1;
		msg += c;
		n   -= c;
		++i;
	}
	assert(i==s);
	while (i<s+k) {
		tx_frame[i].mid = mid;
		tx_frame[i].metad = (s<<12) + i;
		fragdatas[i] = tx_frame[i].fragmentdata;
		++i;
	}
	tfec3_encode(WORDS_PER_FRAGMENT,s,k,fragdatas);
	for (i=s; i<s+k; ++i) {
		tx_frame[i].crc16 = compute_frame_crc(tx_frame+i);
		tx_valid[i] = 1;
	}
	send_count = s+k; /* number of frames to send */
	send_next  = 0;   /* from the start please... */
	return (k*100+(s >> 1))/s;
}

/**
 * Recover lost fragment data of a message
 *
 * Valid received frames from one specific message (all the same message ID)
 * have to be placed at the correct index in the tx_frame buffer and marked
 * as valid via tx_valid. If you received a frame you can check its index via
 * FRAGMENT_INDEX(pointer_to_frame). Check this value and compare it with
 * FRAME_BUFF_SIZE unless you like buffer overflows.
 *
 * @return
 *   the number of data fragments on success (without redundancy),
 *   0 otherwise.
 */
int recover_received_message(void)
{
	int i, s, k, n;
	tfec3_u32 *fragdatas[FRAME_BUFF_SIZE];
	s = -1; /* number of user-data fragments (excluding redundancy) */
	n = 0;  /* number of pointers tfec3_decode should check */
	for (i=0; i<FRAME_BUFF_SIZE; ++i) {
		fragdatas[i] = tx_frame[i].fragmentdata;
		if (tx_valid[i]) {
			if (s<0) s = NUM_DATA_FRAGS(tx_frame+i);
			n = 1+i;
		}
	}
	printf("\n---------------\n%d %d\n",s,k);

	/* Example:
	 * But we did not receive all of'em. #2 and #7 are missing
	 *
	 *       user-data   | redundancy
	 *     0   1   2   3 | 5   6   7
	 *    ---------------+-----------
	 *    yes yes  no yes yes yes  no
	 *
	 * At the receiver side it looks like the sender just generated
	 * two redundancy packets. Hence, s=4, n=6, k=2
	 */
	k = n - s; /* number of redundancy pointers to check */
	return tfec3_decode(WORDS_PER_FRAGMENT,s,k,tx_valid,fragdatas) ? s : 0;
}

/**
 * extracts fragments from frame buffer into a user-supplied buffer
 *
 * @param howmany
 *   number of fragments to extract and concatenate
 * @param target
 *   pointer to target buffer with at least howmany*BYTES_PER_FRAGMENT
 *   free space.
 */
void collect_fragments(int howmany, char target[])
{
	int i;
	for (i=0; i<howmany; ++i) {
		memcpy(target,tx_frame[i].fragmentdata,BYTES_PER_FRAGMENT);
		target += BYTES_PER_FRAGMENT;
	}
}

static void destroy_frame(int whichone)
{
	assert(0<=whichone && whichone<FRAME_BUFF_SIZE);
	memset(tx_frame+whichone,0,sizeof(*tx_frame));
	tx_valid[whichone] = 0;
}

int main(void)
{
	int n, r, i;
	const char* msg =
		"Hello World! This is a m"  /* fragment 0 */
		"essage that will be chop"  /* fragment 1 */
		"ped up into multiple pie"  /* fragment 2 */
		"ces. The pieces called f"  /* fragment 3 */
		"ragments are framed and "  /* fragment 4 */
		"checksummed. Let's see h"  /* fragment 5 */
		"ow that goes...";          /* fragment 6 */
	puts("Preparing a message for sending...");
	n = strlen(msg)+1; /* message size including null terminator */
	r = 20; /* shoot for 20% redundancy */
	r = prepare_send_message(n,msg,r);
	printf("number of frames for message = %i\n",send_count);
	printf("           actual redundancy = %i%%\n",r);
	for (i=0; i<send_count; ++i) {
		print_frame(tx_frame+i);
	}

	puts("Destroying frames (simulated erasure)...");
	destroy_frame(1);
	destroy_frame(3);
	for (i=0; i<send_count; ++i) {
		print_frame(tx_frame+i);
	}

	puts("Trying to recover missing fragments...");
	r = recover_received_message();
	if (r) {
		puts("Success! The message was...");
		for (i=0; i<r; ++i) {
			print_frame(tx_frame+i);
		}
	} else {
		puts("Failure!");
	}
	return 0;
}
